{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "19f52f09",
   "metadata": {},
   "source": [
    "## 突破O(n*lg(n))复杂度的排序算法\n",
    "1. 计数排序\n",
    "2. 基数排序\n",
    "3. 桶排序\n",
    "\n",
    "放弃采用元素比较的方法进行操作。\n",
    "采用计数排序，实际上使用空间换时间，适用于数据列表中元素之间距离较为紧凑（非稀疏数据），同时数据规模适中。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "f64dbe9d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before sort : [82, 11, 39, 100, 97, 54, 78, 49, 34, 78, 26, 82, 32, 25, 12, 58, 39, 75, 90, 2]\n",
      "After sort : [2, 11, 12, 25, 26, 32, 34, 39, 39, 49, 54, 58, 75, 78, 78, 82, 82, 90, 97, 100]\n"
     ]
    }
   ],
   "source": [
    "## 计数排序\n",
    "def counting_sort(A):\n",
    "    k = 0\n",
    "    for element in A:\n",
    "        if isinstance(element, int) is False or element < 0:        # 要求列表元素必须是正整数\n",
    "            raise Exception(\"Element has to be integer and no minus.\")\n",
    "        if element > k:     # 查找最大值元素\n",
    "            k = element\n",
    "    \n",
    "    buffer_array = []\n",
    "    for i in range(0, k + 1):\n",
    "        buffer_array.append(0)\n",
    "    \n",
    "    for element in A:\n",
    "        buffer_array[element] += 1\n",
    "    \n",
    "    # 累加计数次数\n",
    "    for i in range(1, len(buffer_array)):\n",
    "        buffer_array[i] += buffer_array[i - 1]\n",
    "    \n",
    "    sorted_array = []\n",
    "    for i in range(0, len(A)):\n",
    "        sorted_array.append(0)\n",
    "    \n",
    "    # A = A[::-1]\n",
    "    for element in A:\n",
    "        position = buffer_array[element]\n",
    "        sorted_array[position - 1] = element\n",
    "        buffer_array[element] -= 1\n",
    "    return sorted_array\n",
    "\n",
    "import random\n",
    "N = 20\n",
    "A = []\n",
    "for i in range(N):\n",
    "    A.append(random.randint(0, 100))\n",
    "print(\"Before sort : {0}\".format(A))\n",
    "sorted_A = counting_sort(A)\n",
    "print(\"After sort : {0}\".format(sorted_A))\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "env_py38",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
